(1) Field of the Invention
The present invention relates to a privacy communication technique to provide security for information transmission, and more particularly, to a privacy communication technique using elliptic curves.
(2) Description of Related Art
Privacy communication enables a sender to transmit information to an intended receiver alone without leakage to third parties, and a public key cryptosystem(PKC) is one of the methods thereof via a public digital communication network. In PKC, two keys--an enciphering key and a deciphering key--are given to each party; the former is open to the public while the latter is kept in secret. Given that it is relatively easy to manage these public keys, PKC has now become an essential technique when one wishes to communicate with more than one party in secret.
The security for PKC often depends on difficulty of a discrete logarithm problem(DLP) on finite abelian groups, and finite fields have been used as the finite abelian groups. However, owing to a toil of researchers, the time required to solve DLP has been reduced with every advancement they make. The history of such advancement is compiled in "Cryptography: A Prime", Alan G. Konheim, John Wiley & Sons, Inc. Accordingly, a method that uses elliptic curves in place of the finite abelian groups was proposed to maintain the security for PKC against is advancement. This proposed method is described in "A Course in Number Theory and Cryptography", Neal Koblits, Springer-Verlag, 1987, and the DLP on elliptic curves(EDLP) reads:
Let q be a power of a prime number, GF(q) be a finite field, E(GF(g)) be a group of elements of GF(q) on an elliptic curve E, and an element P of E(GF(q)) be a base point, find an integer x such that Q=xP (Q is a given element of E(GF(q)), if such an integer x exists.
The researchers correspondingly began to apply this EDLP to the methods of the privacy communication such as PKC, because if effectively applied, it was envisaged that
1) the speed of communication would be sharply increased without impairing the security, for there had been no solution proposed such that could confer a sub-exponential algorithm on EDLP, PA1 2) the communication in volume would be reduced, PA1 3) a greater number of the finite abelian groups would be available compared with the finite fields. PA1 when m is 191, EQU #E.sub.3 (GF(2.sup.m))=2.sup.191 +1=3.multidot.p.sub.1, PA1 when m is 252, EQU #E.sub.3 (GF(2.sup.m))=2.sup.251 +1=3.multidot.238451.multidot.p.sub.2 PA1 Condition 1: PA1 Condition 2:
However, unlike the finite fields which define DLP, the researchers found it very difficult to construct appropriate elliptic curves which in effect define EDLP, and their interest has shifted to how easily one can construct them. Conventionally, the elliptic curves are constructed by the following method:
1) Method I
With this method, an elliptic curve called a supersingular elliptic curve is constructed. This method is described in "The Implementation of Elliptic Curve Cryptosystems", Alfred Menezes, Scott Vanstone, Auscrypt 90, 1990, and following is the recapitulation thereof. This method consists of 2 steps as is shown in FIG. 1.
(i) Determination of a Prospective Elliptic Curve
Let E.sub.1, E.sub.2, and E.sub.3 be supersingular elliptic curves defined over GF(2) given by EQU E.sub.1 :y.sup.2 +y=x.sup.3 +x+1 EQU E.sub.2 :y.sup.2 +y=x.sup.3 +x EQU E.sub.3 :y.sup.2 +y=x.sup.3
Let E.sub.i (GF(2.sup.m))(i=1-3) be a group consisting of the elements of GF(2.sup.m) on each supersingular elliptic curve, then EQU E.sub.1 (GF(2.sup.m))={x,y.epsilon.GF(2.sup.m).vertline.y.sup.2 +y=x.sup.3 +x+1}U{.infin.} EQU E.sub.2 (GF(2.sup.m))={x,y.epsilon.GF(2.sup.m).vertline.y.sup.2 +y=x.sup.3 +x}U{.infin.} EQU E.sub.3 (GF(2.sup.m))={x,y.epsilon.GF(2.sup.m).vertline.y.sup.2 +y=x.sup.3 }U{.infin.}
(.infin. is an infinite point which is known as a zero element).
As can be seen in the above, the elements of E.sub.i (GF(2.sup.m)) constitute a finite abelian group; for addition is applied among themselves.
Further, let m be an odd number, then the number of E.sub.i (GF(2.sup.m)(i=1-3), or #E.sub.i (GF(2.sup.m), is found as given below by Deu's theorem and Hasse's theorem. ##EQU1## (ii) Determination of a Suitable Extension Degree m
It is known that EDLP is easily solved unless the order of the element P, or the base point, has a large prime factor. Therefore, a necessary and sufficient condition for the element P is that #E.sub.i (GF(2)) has a large prime factor. Thus, m such that satisfies the necessary and sufficient condition is found.
The elliptic curves found in Step (i) and m in Step (ii) are used to construct EDLP. Accordingly, #E.sub.3 (GF(2.sup.m)) factorized, and it is found that :
(p.sub.1 and p.sub.2 are prime numbers.)
This leads to a conclusion that EDLP can be constructed by finding a supersingular elliptic curve defined over E.sub.3 (GF(2.sup.191)) with the base point P whose order has exactly p.sub.1 or E.sub.3 (GF(2.sup.251) with the base point P whose order has exactly p.sup.2. In other words, the enciphering and deciphering keys are made by using these E.sup.3 (GF(2.sup.191)) and the base point P, or E.sup.3 (GF(2.sup.251) and the base point P.
In 1991, however, a solution using a reducing method was proposed. This method is effective in solving EDLP on supersingular elliptic curves, for it confers a sub-exponential algorithm thereon, thereby impairing security for privacy communication.
"Reducing Elliptic Curve Logarithm to Logarithms in a Finite Field", A. Menezes, S. Vanston, and T. Okamoto, STOC, '91, gives an explanation on the reducing method, and it reads:
Let q be a square of a prime number, E an elliptic curve defined over GF(q), E(GF(q)) be a group consisting of elements of GF(q) on the elliptic curve E. Then, EDLP on the elliptic curve having the base point P.epsilon.E(GF(q)) can be solved by reducing it to DLP over an extension field GF(q.sup.r) of GF(q), provided that the order of the base point P is prime to q. EDLP on supersingular elliptic curves, in particular, can be solved by reducing it to the sextic extension field of GF(q) -GF(q.sup.6)- at most.
Attacked by this reducing method, EDLP constructed by Method I can no longer secure PKC unless n of GF(2.sup.n) is increased to a number larger than 256, which in turn causes a steep decrease of the communication speed.
Given these circumstances, another constructing method of EDLP which can secure PKC against this attack was proposed.
2) Method II
With this method, ordinary elliptic curves which defines EDLP unsolvable by the reducing method is constructed. This method is described in "Non-supersingular Elliptic Curve for Public Key Cryptosystems", T. Beth, F. Schaefer, Eurocrypt 91, 1991, and the following is the recapitulation thereof. This method consists of 2 steps as is shown in FIG. 2.
(i) Determination of a Prospective Elliptic Curve
Let E.sub.i (i=4,5) be a non-supersingular, i.e. ordinary, elliptic curve defined over GF(2) given by EQU E.sub.4 :y.sup.2 +xy=x.sup.3 +x.sup.2 +1 EQU E.sub.5 :y.sup.2 +xy=x.sup.3 +1
Let E.sub.i (GF(2.sup.m)) be a group consisting of the elements of GF(2.sup.m)(i=4,5) on each elliptic curve, then the number thereof, or #E.sub.i (GF(2.sup.m)), is found as given below by Deu's theorem and Hasse's theorem. EQU #E.sub.4 (GF(2.sup.m))=1+2.sup.r -{(1+(-7).sup.1/2)/2}.sup.m -{(1-(-7).sup.1/2)/2}.sup.m EQU #E.sub.5 (GF(2.sup.m))=1+2.sup.r -{(-1+(-7).sup.1/2)/2}.sup.m -{(-1-(-7).sup.1/2)/2}.sup.m
(ii) Determination of an Extension Degree m
Let m be an extension degree for E.sub.i (i=4,5) such that it satisfies the two following conditions:
#E.sub.i (GF(2.sup.m)) must have a large prime factor. PA2 Let p be the largest prime factor of #E.sub.i (GF(2.sup.m)), and t be a sufficiently large positive integer, then 2.sup.mk -1 does not have p as a prime factor(k is an arbitrary positive integer smaller than t).
Condition 1 is given to provide #E.sub.i (GF(2.sup.m)) with a large prime factor and Condition 2 to increase t as far as possible, for the security increases as t becomes larger; more particularly, when EDLP on the elliptic curve defined over E.sub.i (GF(2.sup.m) is reduced to DLP on the elliptic curve defined over the extension field of GF(2.sup.m), the extension degree m becomes larger than t.
The elliptic curves found in Step (i) and m in Step (ii) are used to construct EDLP. Accordingly, #E.sub.4 (GF(2.sup.m)) is factorized, and it is found that when m is 107, #E.sub.4 (GF(2.sup.m))=2.multidot.p.sub.3 (p.sub.3 is a prime number).
It is easy to calculate 2.sup.mk -1 with today's advanced computers, and to prove that 2.sup.mk -1 does not have p.sub.3 as a prime factor when k is a number from 1 to 6. Thus, it can be concluded that an ordinary elliptic curve defined over E.sub.4 (GF(2.sup.107) with the base point P whose order has exactly p.sub.3 must be found to construct EDLP, on which the security of PKC depends. In other words, the enciphering and deciphering keys are made by using these E.sub.4 (GF(2.sup.107)) and the base point P.
PKC using such ordinary elliptic curves is secure when n of GF(2.sup.n) is a number more than 100 with the level of today's computer technology. Yet, such security can not be guaranteed without increasing n endlessly to meet rapid progress in this field, which in turn reduces the speed of privacy communication. Therefore, a method of constructing elliptic curves such that define EDLP unsolvable by the reducing method has been sought after.